1. Field of the Invention
The present invention relates to a logic simulation system to be used for a simulation of logic circuits in designing and a verification of a digital system using logic circuits.
2. Description of the Background Art
In a large scale computer development project, the reduction of time and cost required for the development is becoming an increasingly important issue, and to this end, the verification of the functions and the performance of the developed system by the simulation plays a crucially important role.
In this regard, in the designing of a digital system using logic circuits, it has become almost indispensable to carry out the simulation of logic circuits in order to shorten the time required for developing the system as well as to achieve a high level of perfection.
For such simulation of logic circuits, a simulation by software has been utilized conventionally, but this approach has a drawback that it requires a considerable amount of time for executing an enormous amount of calculations required, such that the turn-around time of the simulation has been considerably long, especially for a large scale circuit.
In order to resolve this problem, there has been a development of a dedicated hardware simulation engine for facilitating such a simulation of the logic circuits.
In general, the simulation engine can be classified into two types including: an event driven type simulation engine in which the simulation is achieved by processing events in the logic circuits by a dedicated simulation processor; and an emulator for carrying out an emulation in which the logic circuits are mapped onto programmable elements such as field programmable gate arrays. This type of a conventional hardware emulator has been disclosed in Japanese Patent Application Laid Open No. 2-245831 (1990), for example.
Now, the conventional event driven type simulation engine has an advantage that it can handle a very large scale circuit, but it has been associated with a problem that it is difficult to realize a high speed simulation as the parallelism of the simulation target can be retained only limitedly because of a limited number of processors that can be provided in such an event driven type simulation engine.
On the contrary, the hardware emulator has an advantage that it can realize a high speed simulation as the parallelism of the simulation target can be retained completely, but it has been associated with a problem that it cannot handle a very large scale circuit because the size of the circuit that can be simulated in the hardware emulator is limited by the size of the hardware emulator itself.
In further detail, the hardware emulator generally comprises a plurality of mutually connected logic blocks in which a high speed logic simulation can be achieved by mapping the simulation target logic circuits onto logic blocks such that each logic block can execute the same operation as the mapped part of the logic circuits. Such a logic block can be realized for example by a field programmable gate array (FPGA) formed by a plurality of programmable elements in which each programmable element simulates the operation of one or more of the circuit elements of the simulation target logic circuits.
In such a hardware emulator, the mapping of the simulation target logic circuits onto the programmable elements and the determination of the connections among the programmable elements have been achieved by a compiler. The program data obtained as a result of the mapping by the compiler are usually loaded into a memory provided in the emulator before the simulation takes place, and utilized by the emulator to determine the operations of the programmable elements during the simulation.
Now, one of the major problem associated with such a hardware emulator is the enormous time required for the compiling by the compiler. This problem is caused by the following reason. Namely, a typical conventionally used is emulator architecture in the form of a mesh structure in which only the adjacent FPGAs are interconnected has a very limited degrees of freedom concerning the wirings among the FPGAs. In addition, most of the FPGAs are manufactured for the implementation purpose, so that they also have only a limited degrees of freedom concerning their wirings. Consequently, in order to increase the circuit filling rate (an average number of circuit elements allocated to each programmable element) for the FPGAs, a key problem is the manner of realizing the mapping of the simulation target when only the limited degrees of freedom concerning the wirings is available.
For this key problem, the most efficient solution conventionally known is the probabilitistic algorithm such as the simulated annealing in which the optimization is repeated until the desired mapping can be realized. However, in such a probabilitistic approach, the time required for the mapping becomes enormous as the size of the logic circuit to be simulated increases, such that there are cases in which several days are required for the compiling of the logic circuit in the size of 1M gates, For example. Thus, it has been difficult to realize a truly efficient mapping scheme in the hardware emulator having only limited degrees of freedom concerning the wirings.
The increase of the time required for the compiling in turn increases the turn-around time of the simulation, so that the realization of a high speed mapping algorithm is extremely important.
Moreover, for the emulator with a given number of programmable elements, the size of the logic circuit that can be simulated Is proportional to the circuit filling rate realizable, so that the low circuit filling rate implies a severe limitation on the size of the logic circuit that can be simulated. Consequently, it is important to improve the circuit filling rate for the programmable elements by realizing a highly effective mapping scheme.
On the other hand, one of many conventionally known propositions for the realization of a high speed simulation is the level sort scheme.
This level sort scheme is a scheme for determining an order of evaluations of gates in advance such that the evaluations during the actual simulation can be carried out in accordance with this predetermined static order. Here, the evaluation order in the level sort scheme is determined by the rule that "the evaluation of a gate g is carried out only after the evaluation of the gate on the input side of this gate g is finished", and it is aimed at the calculation of a final value for a combinational circuit portion of a synchronous circuit in a stable circuit operation state.
Now, such a conventional level sort scheme assumes that the combinational circuit portion is designed to contain no loop so that the model of the combinational circuit portion also contains no loop. However, in practice, there are cases in which the combinational circuit portion is designed to contain some loops for various practical reasons, and in such cases the evaluation order cannot be determined by the simple rule of the conventional level sort scheme as mentioned above, so that the conventional level sort scheme has actually been inapplicable to such cases.